package fun.coding.leetcode;

import java.util.Arrays;
import java.util.List;

import fun.coding.baozi.practice.BinaryTreeHelper;

public class ConstructBinaryTreeFromInorderAndPostorderTraversal {

	public static void main(String[] args) {
		/*
		 *             1
		 *          2     3
		 *        4  5      6
		 *          
		 *   in:   4 2 5 1 3 6
		 *   post: 4 5 2 6 3 1   
		 * 
		 */
		
		ConstructBinaryTreeFromInorderAndPostorderTraversal c = new ConstructBinaryTreeFromInorderAndPostorderTraversal();
		int[] inorder = {4, 2, 5, 1, 3, 6};
		int[] postorder = {4, 5, 2, 6, 3, 1};
		
		TreeNode root = c.buildTree(inorder, postorder);
		List<String> actual = BinaryTreeHelper.serializeBinaryTree(root);
		String[] expected = {"1", "2", "3", "4", "5", "#", "6"};
		BinaryTreeHelper.deserializeBinaryTree(Arrays.asList(expected));
		
		assert actual.equals(expected);
	}

	private int index = -1;
	
	public TreeNode buildTree(int[] inorder, int[] postorder) {
		if (inorder == null || postorder == null || inorder.length == 0 || postorder.length == 0) return null;
		
		if (inorder.length != postorder.length) return null;
		
		this.index = inorder.length -1;
		return helper(inorder, 0, inorder.length - 1, postorder);
	}
	
	public TreeNode helper(int[] inorder, int start, int end, int[] postorder) {
		if (start > end) return null;
		
		int rootIndex = -1;
		for (int i = start; i <= end; i++) {
			if (inorder[i] == postorder[this.index]) {
				rootIndex = i;
				break;
			}
		}
		
		TreeNode root = new TreeNode(inorder[rootIndex]);
		this.index--;
		
		root.right = helper(inorder, rootIndex + 1, end, postorder);
		root.left = helper(inorder, start, rootIndex - 1, postorder);
		
		return root;
	}

}
